namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0109. 有序链表转换二叉搜索树")]
    public class No0109_SortedListToBST : AbsBaseTestItem
    {
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        /*
        给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
        本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
        */

        public override void OnTest()
        {
            Assert.TestExe(SortedListToBST,
                new ListNode(-10,
                    new ListNode(-3,
                        new ListNode(0,
                            new ListNode(5,
                                new ListNode(9))))),
                new TreeNode(0,
                    left: new TreeNode(-3,
                        left: new TreeNode(-10)),
                    right: new TreeNode(9,
                        left: new TreeNode(5))));

            Assert.TestExe(SortedListToBST_2,
                new ListNode(-10,
                    new ListNode(-3,
                        new ListNode(0,
                            new ListNode(5,
                                new ListNode(9))))),
                new TreeNode(0,
                    left: new TreeNode(-3,
                        left: new TreeNode(-10)),
                    right: new TreeNode(9,
                        left: new TreeNode(5))));
        }

        /// <summary>
        /// 方法一：分治
        /// </summary>
        public TreeNode SortedListToBST(ListNode head)
        {
            TreeNode buildTree(ListNode left, ListNode right)
            {
                if (left == right)
                {
                    return null;
                }
                ListNode mid = getMedian(left, right);
                TreeNode root = new TreeNode(mid.val);
                root.left = buildTree(left, mid);
                root.right = buildTree(mid.next, right);
                return root;
            }
            ListNode getMedian(ListNode left, ListNode right)
            {
                ListNode fast = left;
                ListNode slow = left;
                while (fast != right && fast.next != right)
                {
                    fast = fast.next;
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
            return buildTree(head, null);
        }

        /// <summary>
        /// 方法二：分治 + 中序遍历优化
        /// </summary>
        public TreeNode SortedListToBST_2(ListNode head)
        {
            ListNode globalHead;
            int getLength(ListNode head)
            {
                int ret = 0;
                while (head != null)
                {
                    ++ret;
                    head = head.next;
                }
                return ret;
            }
            TreeNode buildTree(int left, int right)
            {
                if (left > right)
                {
                    return null;
                }
                int mid = (left + right + 1) / 2;
                TreeNode root = new TreeNode();
                root.left = buildTree(left, mid - 1);
                root.val = globalHead.val;
                globalHead = globalHead.next;
                root.right = buildTree(mid + 1, right);
                return root;
            }
            globalHead = head;
            int length = getLength(head);
            return buildTree(0, length - 1);
        }
    }
}
